#include "stdafx.h"
#include "HashTable.h"

HashTableEntry:: HashTableEntry()
{
	m_pNext = NULL;
	m_hashValue = 0;
}

HashTableEntry::~ HashTableEntry()
{
}

unsigned HashTable::s_primes [] = {53, 97, 193, 389, 
	769, 1543, 3079, 6151,
	12289, 24593, 49157, 98317,
	196613, 393241, 786433, 1572869,
	3145739, 6291469, 12582917, 25165843,
	50331653, 100663319, 201326611, 402653189,
	805306457, 1610612741};

HashTable::HashTable()
{
	m_Table = NULL;
	m_nLength = 0;
	m_nEntries = 0;
	m_nLimit = 0;
	m_PrimeIdx = -1;
	m_fLoad = 0.5;
}

HashTable::~HashTable()
{
	if (m_Table)
	{
		delete [] m_Table;
		m_Table = NULL;
	}
}

HashTableEntry** HashTable::Bucket(unsigned hashValue)
{
	return &m_Table[hashValue % m_nLength];
}

bool HashTable::Grow(unsigned size)
{
	unsigned nPrimes = sizeof(s_primes)/sizeof(s_primes[0]);
	if (m_PrimeIdx == (int)nPrimes - 1)
		return true;

	if (m_nLimit > size)
		return true;

	int primeIdx = m_PrimeIdx;
	unsigned newLen = 0;
	unsigned newLoadLimit = 0;
	do 
	{
		newLen = s_primes[++primeIdx];
		newLoadLimit = (unsigned)(m_fLoad * newLen);
	} while ((newLoadLimit <= size) && (primeIdx < nPrimes));

	HashTableEntry** newTable = NULL;
	if (newTable = new HashTableEntry*[newLen])
	{
		memset(newTable, 0, newLen * sizeof(HashTableEntry*));
		for (unsigned i = 0; i < m_nLength; ++i)
		{
			HashTableEntry* element = m_Table[i];
			while (element)
			{
				HashTableEntry* next = element->GetNext();
				unsigned newIdx = element->GetHashCode()  % newLen;
				element->SetNext(newTable[newIdx]);
				newTable[newIdx] = element;

				element = next;
			}
		}

		if (m_Table)
			delete [] m_Table;
		m_Table = newTable;

		m_nLength = newLen;
		m_PrimeIdx = primeIdx;
		m_nLimit = newLoadLimit;

		return true;
	}

	return false;
}

void HashTable::Insert(HashTableEntry* pEntry)
{
	if (!m_Table || m_nEntries >= m_nLimit)
		Grow(m_nEntries + 1);

	++m_nEntries;
	pEntry->SetHashCode(pEntry->CalcHashCode());

	HashTableEntry** pBucket = Bucket(pEntry->GetHashCode());
	pEntry->SetNext(*pBucket);
	*pBucket = pEntry;
}

HashTableEntry* HashTable::Remove(HashTableEntry* pEntry)
{
	HashTableEntry** pPos = FindP(pEntry);
	if ((!pPos) || (!*pPos))
		return NULL;

	--m_nEntries;

	HashTableEntry* pResult = *pPos;
	*pPos = pResult->GetNext();
	pResult->SetNext(NULL);
	return pResult;
}

HashTableEntry* HashTable::Find(HashTableEntry* pEntry)
{
	if (!m_Table)
		return NULL;

	unsigned hashValue = pEntry->CalcHashCode();
	HashTableEntry* pBucket = *(Bucket(hashValue));
	while (pBucket)
	{
		if (pBucket->Equal(pEntry))
		{
			return pBucket;
		}

		pBucket = pBucket->GetNext();
	}

	return pBucket;
}

HashTableEntry** HashTable::FindP(HashTableEntry* pEntry)
{
	if (!m_Table)
		return NULL;

	unsigned hashValue = pEntry->CalcHashCode();
	HashTableEntry** pBucket = Bucket(hashValue);
	while (*pBucket)
	{
		if ((*pBucket)->Equal(pEntry))
		{
			return pBucket;
		}

		pBucket = (*pBucket)->GetNextP();
	}

	return pBucket;
}